partiels/091105/partiel_Mathsdis_S2_Novembre 09.tex

   1 \documentclass[12pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  10 \usepackage[dvips]{graphics}
  11 \usepackage{epsfig}
  12 \usepackage{calc}
  13 \usepackage{tabls}
  14 \usepackage{slashbox}
  15 \usepackage{times}
  16 \usepackage{tabularx}
  17 \usepackage{textcomp}
  18 \usepackage{pst-all}
  19 \usepackage[a4paper]{geometry}
  20 \input{symboles.sty}
  21
  22
  23 \date{}
  24 \geometry{hmargin=1cm, vmargin=1.5cm}\begin{document}
  25 \title{
  26 Département d'informatique.\\
  27 Partiel de  mathématiques discrètes. \\
  28 Semestre 2 (Novembre 09)\\
  29 }
  30 \maketitle
  31
  32 Aucun document autorisé.
  33
  34 \begin{tabular}{ll}
  35 Nom: &......................................... \\
  36 Prénom: &.........................................\\
  37 \end{tabular}
  38 \section{QCM}
  39 Cette partie contient 30 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\
  40
  41 Q. 1. Soit la démonstration  syntaxique suivante: \newline
  42 \begin{center}
  43 \begin{tabular}{lll}
  44 \multicolumn{3}{l}{Démonstration sous hypothèses
  45 $\{\neg B \Rightarrow \neg A, A\}$}\\
  46 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
  47 2.&$A$ &$H_2$ \\
  48 3.&\_\_\_\_\_ & \_\_\_\_\_ \\
  49 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
  50 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
  51 6.& $ \neg \neg B \Rightarrow B $&Axiome 9 ($B/P$).\\
  52 7.& $B$ &mp entre 5. et 6. \\
  53 Conclusion
  54
  55 \end{tabular}
  56 \end{center}
  57
  58 \noindent La démonstration est correcte si en 3. et 4. on a:
  59 \begin{tabular}{lll}
  60 3.&$A \Rightarrow (\neg B \Rightarrow A)$ &Axiome 1 ($A/P,\neg B /Q$). \\
  61 4.&$\neg B \Rightarrow A $ &modus ponens entre 2. et 3.
  62 \end{tabular}
  63 \\
  64
  65 Q. 2. \og $A$ à moins que  $B$ \fg{}
  66 peut-elle être représentée par $ \neg A \Rightarrow B$?
  67         \\
  68
  69 Q. 3.  La négation de \og ce triangle est rectangle donc ce triangle possède un angle droit \fg{}
  70 est-elle  \og ce triangle ne possède pas un angle droit et pourtant il est rectangle\fg{}
  71         \\
  72
  73 Q. 4. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
  74         Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
  75 \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
  76 $ p \lor q $?
  77         \\
  78
  79 Q. 5.
  80 \og Il est faux qu'il ne fait pas froid ou qu'il pleut \fg{}
  81 est-elle équivalente à   \og il fait froid mais il ne pleut pas \fg{}?
  82         \\
  83
  84 Q. 6.  Soit $p$, $q$, $r$ trois variables propostionnelles.
  85         L'énoncé suivant est-il une tautologie?
  86 $
  87 (p \Rightarrow q) \land (p \lor r) \Rightarrow q \lor r$.
  88         \\
  89
  90 Q. 7. Une formule propositionnelle $F$ est  conséquence logique d'une antilogie.
  91          L'affirmation suivante est-elle vraie:
  92 \og  $F$ est donc une tautologie \fg{}?
  93         \\
  94
  95 Q. 8. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement à \og il est grand \fg{} et \og il est beau \fg{}.
  96         Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
  97 \og il est grand ou il est petit et beau \fg{} peut-elle s'écrire
  98 $ (p \lor \neg p) \land q $?
  99         \\
 100
 101 Q. 9.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 102         L'énoncé suivant est-il une tautologie?
 103 $
 104 (p \Rightarrow q) \lor p \lor r \Rightarrow q \lor r$.
 105         \\
 106
 107 Q. 10. \og $A$ à moins que  $B$ \fg{}
 108 peut-elle être représentée par $ B \Rightarrow A $?
 109         \\
 110
 111 Q. 11.  L'affirmation \og il fait beau aujourd'hui  donc il ne pleuvra pas dans dix jours \fg{}
 112 est-elle une proposition?
 113         \\
 114
 115 Q. 12.
 116 Soit la démonstration  syntaxique suivante: \newline
 117 \begin{center}
 118 \begin{tabular}{lll}
 119 \multicolumn{3}{l}{Démonstration sous hypothèses
 120 $\{\neg B \Rightarrow \neg A, A\}$}\\
 121 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 122 2.&$A$ &$H_2$ \\
 123 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
 124 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 125 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 126 6.&$\neg \neg B \Rightarrow B $&Axiome 9 ($B/P$).\\
 127 7.& $B$ &mp entre 5. et 6.\\
 128 Conclusion
 129 \end{tabular}
 130 \end{center}
 131
 132 \noindent La démonstration est correcte si en 3. et 4. on a: \newline
 133 \begin{tabular}{lll}
 134 3.&$ (\neg B \Rightarrow \neg A )\Rightarrow (\neg \neg A \Rightarrow  \neg \neg B) $ &théoreme de la contraposée ($\neg B/P, \neg A /Q$) \\
 135 4.&$\neg \neg A \Rightarrow A $ &Axiome 9 ($A/P $).
 136 \end{tabular}
 137 \\
 138
 139 Q. 13. \og $A$ à moins que  $B$ \fg{}
 140 peut-elle être représentée par $ B \lor A $?
 141         \\
 142
 143 Q. 14. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
 144 est-elle suffisante pour affirmer que
 145 \og sa mère est anglaise ou  son père n'est pas français \fg{}?
 146         \\
 147
 148 Q. 15.
 149 Soit la démonstration  syntaxique suivante: \newline
 150 \begin{center}
 151 \begin{tabular}{lll}
 152 \multicolumn{3}{l}{Démonstration sous hypothèses
 153 $\{\neg B \Rightarrow \neg A, A\}$}\\
 154 1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
 155 2.&$A$ &$H_2$ \\
 156 3.&\_\_\_\_\_ &\_\_\_\_\_ \\
 157 4.&\_\_\_\_\_ &\_\_\_\_\_ \\
 158 5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
 159 6.&$\neg \neg B \Rightarrow B$ &Axiome 9 ($B/P$).\\
 160 7.& $B$ &mp entre 5. et 6.\\
 161 Conclusion
 162 \end{tabular}
 163 \end{center}
 164
 165 \noindent Si elle était complète cela permetrait de
 166 démontrer syntaxiquement
 167 $(\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B)
 168 $.
 169  L'assertion proposée est vraie ou fausse ?
 170 \\
 171
 172 Q. 16.  L'affirmation \og le Vesuve a ravagé la ville de Pompei en 1999 \fg{}
 173 est-elle une proposition?
 174         \\
 175
 176 Q. 17. \og $B$ seulement si  $A$ \fg{}
 177 peut-elle être représentée par $ \neg A \Rightarrow B $?
 178         \\
 179
 180 Q. 18. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
 181          L'affirmation suivante est-elle vraie:
 182 \og  $F$ est donc une antilogie \fg{}?
 183         \\
 184
 185 Q. 19.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 186         L'énoncé suivant est-il une tautologie?
 187 $(p \lor q) \land r \Rightarrow (p \lor r) \land (q \lor r)$.
 188         \\
 189
 190 Q. 20.  La négation de \og ce triangle est rectangle donc ce triangle possède un angle droit \fg{}
 191 est-elle  \og ce triangle n'est pas rectangle donc ce triangle ne possède pas un angle droit \fg{} ?
 192         \\
 193
 194 Q. 21.  Soit $p$ et $q$, deux variables propostionnelles.
 195         L'énoncé suivant est-il une tautologie?
 196 $
 197 (p \land ( p \lor q)) \Leftrightarrow p$.
 198         \\
 199
 200 Q. 22. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
 201          L'affirmation suivante est-elle vraie:
 202 \og  $F$ est donc une antilogie \fg{}?
 203         \\
 204
 205 Q. 23. Une formule propositionnelle $F$ est conséquence logique d'une antilogie.
 206          L'affirmation suivante est-elle vraie:
 207 \og  $F$ est donc une antilogie \fg{}?
 208         \\
 209
 210 Q. 24.
 211 \og \emph{Si la paix survient, alors il y aura une crise économique
 212 à moins que le pays se dote d'armes nouvelles ou bien exécute
 213 un large programme d'investissement intérieur dans les secteurs de
 214 l'enseignement, de la santé et de la lutte contre la pauvreté.
 215 Il n'est pas possible de se mettre d'accord sur les objectifs
 216 que peut se donner un large programme d'investissement intérieur.
 217 Donc si la paix survient et qu'il n'y a pas de crise économique,
 218 le pays doit se doter d'armes nouvelles.} \fg{}
 219          Le raisonnement proposé est-il correct?
 220         \\
 221
 222 Q. 25. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
 223          L'affirmation suivante est-elle vraie:
 224 \og  $F$ est donc une tautologie \fg{}?
 225         \\
 226
 227 Q. 26. \og Il est faux que sa mère est anglaise ou que son père est français \fg{}
 228 est-elle équivalente à
 229 \og sa mère est anglaise ou son père n'est pas français \fg{}?
 230         \\
 231
 232 Q. 27. Une formule propositionnelle $F$ a pour conséquence logique une tautologie.
 233          L'affirmation suivante est-elle vraie:
 234 \og  On ne peut donc rien dire de $F$ \fg{}?
 235         \\
 236
 237 Q. 28. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
 238          L'affirmation suivante est-elle vraie:
 239 \og  $F$ est donc une tautologie \fg{}?
 240         \\
 241
 242 Q. 29.  Soit $p$, $q$, $r$ trois variables propostionnelles.
 243         L'énoncé suivant est-il une tautologie?
 244 $(p \lor q) \land r \Leftarrow (p \lor r) \land (q \lor r)$.
 245         \\
 246
 247 Q. 30. Une formule propositionnelle $F$ est conséquence logique d'une tautologie.
 248          L'affirmation suivante est-elle vraie:
 249 \og  On ne peut donc rien dire de $F$ \fg{}?
 250         \\
 251
 252 \section{Déduction syntaxique}
 253
 254 Dans le système \og PR \fg{} et en se servant éventuellement des théorèmes
 255 déjà démontrés dans le cours, démontrer syntaxiquement
 256 les deux formules propositionnelles suivantes:
 257 \begin{enumerate}
 258 \item
 259 $
 260   (A \Rightarrow B) \Rightarrow
 261   ((A \Rightarrow C) \Rightarrow (A \Rightarrow B \land C))
 262 $
 263
 264 \item
 265 $
 266 (A \Rightarrow B) \Rightarrow
 267 ((C \Rightarrow \neg B) \Rightarrow  (A \Rightarrow \neg C))
 268 $
 269 \end{enumerate}
 270
 271 \section{Conséquences logiques}
 272 Pour chacun des raisonnements suivants,
 273 \begin{itemize}
 274 \item réécrire le problème dans une  logique  propositionnelle;
 275 \item dire si la conclusion est une conséquence logique des hypothèses en justifiant.
 276 \end{itemize}
 277
 278 \begin{enumerate}
 279 \item Si je n'étudie pas, j'ai des remords.
 280   Mais si je ne vis pas à fond ma jeunesse, j'ai aussi des remords.
 281   Or je n'ai pas de remords.
 282   C'est donc que j'étudie tout en vivant à fond ma jeunesse.
 283 \item Si Jean n'a pas rencontré Pierre l'autre nuit,
 284 c'est que Pierre est le meurtrier ou que Jean est un menteur.
 285 Si Pierre n'est pas le meurtrier, alors Jean n'a pas rencontré Pierre
 286 l'autre nuit et le crime a eu lieu après minuit.
 287 Si le crime a eu lieu après minuit, alors Pierre est
 288 le meurtrier ou Jean n'est pas un menteur.
 289 Donc Pierre est le meurtrier
 290 \end{enumerate}
 291
 292 \section*{Annexes : Axiomes de PR}
 293
 294 \begin{itemize}\item Axiome 1 : $P\imp (Q\imp P)$
 295 \item Axiome 2 : $(P\imp Q)\imp((P\imp(Q
 296 \imp R))\imp (P\imp R))$
 297 \item Axiome 3 : $P\imp(Q\imp P\et Q)$
 298 \item Axiome 4 : $P\et Q\imp P$
 299 \item Axiome 5 : $P\et Q\imp Q$
 300 \item Axiome 6 : $P\imp P\ou Q$
 301 \item Axiome 7 : $Q\imp P\ou Q$
 302 \item Axiome 8: $(P\imp R)\imp((Q\imp R) \imp(P\ou Q\imp R))$
 303 \item Axiome 9: $\non\non P\imp P$
 304 \item Axiome 10: $(P\imp Q)\imp((P\imp\non Q)$
 305 \item Axiome 11 : $(P\imp Q)\imp((Q\imp P)\imp(P\eqv Q))$
 306 \item Axiome 12 : $(P\eqv Q)\imp(P\imp Q)$
 307 \item Axiome 13 : $(P\eqv Q)\imp(Q\imp P)$
 308 \end{itemize}
 309
 310
 311
 312 \section*{Réponses au QCM}
 313
 314 \begin{large}
 315 \begin{center}
 316 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
 317 \hline
 318 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
 319 \hline
 320 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
 321 \hline
 322 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
 323 \hline
 324 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
 325 \hline
 326 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
 327 \hline
 328 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
 329 \hline
 330 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
 331 \hline
 332 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
 333 \hline
 334 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
 335 \hline
 336 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
 337 \hline
 338 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
 339 \hline
 340 \end{tabular}
 341 \end{center}
 342 \end{large}
 343
 344
 345
 346
 347 \end{document}